//
// Created by last on 2025/9/20.
//
#include <iostream>
#include <vector>
#include <array>
#include <random>
#include <chrono>
#include <algorithm>
#include <string>
#include <iomanip>
#include "../include/Sorter.hpp"

// 生成随机整数的函数
void generateRandomInts(int* arr, size_t n, int min = 0, int max = 10000) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(min, max);

    for (size_t i = 0; i < n; ++i) {
        arr[i] = dis(gen);
    }
}

// 生成随机浮点数的函数
void generateRandomDoubles(double* arr, size_t n, double min = 0.0, double max = 1.0) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(min, max);

    for (size_t i = 0; i < n; ++i) {
        arr[i] = dis(gen);
    }
}

// 生成随机字符串的函数
void generateRandomStrings(std::string* arr, size_t n, int length = 10) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis('a', 'z');

    for (size_t i = 0; i < n; ++i) {
        std::string str;
        str.reserve(length);
        for (int j = 0; j < length; ++j) {
            str.push_back(static_cast<char>(dis(gen)));
        }
        arr[i] = str;
    }
}

// 测试函数模板
template <typename T, typename Generator>
void runSortTest(const std::string& testName, size_t size, Generator generator) {
    // 添加大小检查
    if (size == 0) {
        std::cout << "警告: 跳过大小为0的测试: " << testName << std::endl;
        return;
    }

    try {
        // 准备测试数据
        std::vector<T> data1(size);
        std::vector<T> data2(size);

        // 生成随机数据
        generator(data1.data(), size);
        std::copy(data1.begin(), data1.end(), data2.begin());

        std::cout << "=== " << testName << " (大小: " << size << ") ===" << std::endl;

        // 测试标准库排序
        auto start = std::chrono::high_resolution_clock::now();
        std::sort(data1.begin(), data1.end());
        auto end = std::chrono::high_resolution_clock::now();
        auto stdTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        // 测试Sorter排序 - 添加异常处理
        start = std::chrono::high_resolution_clock::now();
        try {
            Sorter sorter(data2);
            sorter.sort();
        } catch (const std::exception& e) {
            std::cout << "Sorter排序出错: " << e.what() << std::endl;
            return;
        }
        end = std::chrono::high_resolution_clock::now();
        auto sorterTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        // 验证排序结果
        bool sortedCorrectly = false;
        try {
            Sorter sorterCheck(data2);
            sortedCorrectly = sorterCheck.is_asc_sorted();
        } catch (const std::exception& e) {
            std::cout << "验证排序结果出错: " << e.what() << std::endl;
        }

        // 输出结果
        std::cout << "标准库std::sort耗时: " << stdTime << " μs" << std::endl;
        std::cout << "Sorter排序耗时: " << sorterTime << " μs" << std::endl;
        if (stdTime > 0) {
            std::cout << "速度比率: " << std::fixed << std::setprecision(2)
                      << static_cast<double>(sorterTime) / stdTime << std::endl;
        } else {
            std::cout << "速度比率: 无法计算 (除零)" << std::endl;
        }
        std::cout << "排序结果正确: " << (sortedCorrectly ? "是" : "否") << std::endl;
        std::cout << std::endl;
    } catch (const std::exception& e) {
        std::cout << "测试 " << testName << " 出错: " << e.what() << std::endl;
    }
}

// 测试不同数据分布
template <typename T>
void runDistributionTests(const std::string& typeName) {
    const size_t size = 100000;

    // 随机数据
    runSortTest<T>(typeName + " - 随机数据", size, [](T* arr, size_t n) {
        if constexpr (std::is_same_v<T, int>) {
            generateRandomInts(arr, n);
        } else if constexpr (std::is_same_v<T, double>) {
            generateRandomDoubles(arr, n);
        } else if constexpr (std::is_same_v<T, std::string>) {
            generateRandomStrings(arr, n);
        }
    });

    // 部分有序数据
    runSortTest<T>(typeName + " - 部分有序数据", size, [](T* arr, size_t n) {
        if constexpr (std::is_same_v<T, int>) {
            generateRandomInts(arr, n);
            // 对前90%的数据进行排序
            std::sort(arr, arr + static_cast<size_t>(n * 0.9));
        } else if constexpr (std::is_same_v<T, double>) {
            generateRandomDoubles(arr, n);
            std::sort(arr, arr + static_cast<size_t>(n * 0.9));
        } else if constexpr (std::is_same_v<T, std::string>) {
            generateRandomStrings(arr, n);
            std::sort(arr, arr + static_cast<size_t>(n * 0.9));
        }
    });

    // 大量重复数据
    runSortTest<T>(typeName + " - 大量重复数据", size, [](T* arr, size_t n) {
        if constexpr (std::is_same_v<T, int>) {
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_int_distribution<> dis(0, 10); // 只有11个不同的值
            for (size_t i = 0; i < n; ++i) {
                arr[i] = dis(gen);
            }
        } else if constexpr (std::is_same_v<T, double>) {
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_real_distribution<> dis(0.0, 0.1); // 小范围
            for (size_t i = 0; i < n; ++i) {
                arr[i] = dis(gen);
            }
        } else {
            // 对于字符串，使用少量不同的字符串
            std::string patterns[] = {"abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "vwx", "yz"};
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_int_distribution<> dis(0, sizeof(patterns)/sizeof(patterns[0])-1);
            for (size_t i = 0; i < n; ++i) {
                arr[i] = patterns[dis(gen)];
            }
        }
    });
}

// 测试不同容器类型
void runContainerTests() {
    const size_t size = 10000;

    std::cout << "=== 测试不同容器类型 ===" << std::endl;

    // 测试std::vector
    std::vector<int> vecData(size);
    generateRandomInts(vecData.data(), size);

    auto start = std::chrono::high_resolution_clock::now();
    std::sort(vecData.begin(), vecData.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto stdTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

    start = std::chrono::high_resolution_clock::now();
    try {
        Sorter sorterVec(vecData);
        sorterVec.sort();
    } catch (const std::exception& e) {
        std::cout << "std::vector测试出错: " << e.what() << std::endl;
    }
    end = std::chrono::high_resolution_clock::now();
    auto sorterTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

    std::cout << "std::vector<int> - 标准库: " << stdTime << " μs, Sorter: "
              << sorterTime << " μs, 比率: "
              << static_cast<double>(sorterTime)/stdTime << std::endl;

    // 测试std::array
    std::array<int, 10000> arrData;
    generateRandomInts(arrData.data(), size);

    start = std::chrono::high_resolution_clock::now();
    std::sort(arrData.begin(), arrData.end());
    end = std::chrono::high_resolution_clock::now();
    stdTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

    start = std::chrono::high_resolution_clock::now();
    try {
        Sorter sorterArr(arrData);
        sorterArr.sort();
    } catch (const std::exception& e) {
        std::cout << "std::array测试出错: " << e.what() << std::endl;
    }
    end = std::chrono::high_resolution_clock::now();
    sorterTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

    std::cout << "std::array<int, 10000> - 标准库: " << stdTime << " μs, Sorter: "
              << sorterTime << " μs, 比率: "
              << static_cast<double>(sorterTime)/stdTime << std::endl;

    std::cout << std::endl;
}

// 测试不同大小
void runSizeTests() {
    std::cout << "=== 测试不同数据大小 ===" << std::endl;

    const size_t sizes[] = {1000, 10000, 100000, 1000000};

    for (size_t size : sizes) {
        std::vector<int> data1(size);
        std::vector<int> data2(size);

        generateRandomInts(data1.data(), size);
        std::copy(data1.begin(), data1.end(), data2.begin());

        auto start = std::chrono::high_resolution_clock::now();
        std::sort(data1.begin(), data1.end());
        auto end = std::chrono::high_resolution_clock::now();
        auto stdTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        start = std::chrono::high_resolution_clock::now();
        Sorter sorter(data2);
        sorter.sort();
        end = std::chrono::high_resolution_clock::now();
        auto sorterTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

        std::cout << "大小 " << size << " - 标准库: " << stdTime << " μs, Sorter: "
                  << sorterTime << " μs, 比率: "
                  << static_cast<double>(sorterTime)/stdTime << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    system("chcp 65001");
    std::cout << "开始排序算法性能对比测试..." << std::endl << std::endl;

    // 测试不同数据类型
    runDistributionTests<int>("整型");
    runDistributionTests<double>("双精度浮点型");
    runDistributionTests<std::string>("字符串");

    // 测试不同容器类型
    runContainerTests();

    // 测试不同数据大小
    runSizeTests();

    std::cout << "测试完成!" << std::endl;
    return 0;
}